# Python 2.6.4
# Project Euler, Problem 142
# Copyright 2010 Talha Zaman

sq = [i**2 for i in range(1,1000)]
lookup = set(sq)
done = False
for i in range(920, len(sq)):
    for j in range(0, i):
        if (sq[i]-sq[j])%2 == 0:
            x = (sq[i]+sq[j])/2
            y = x-sq[j]
            k, l, found = j+1, i-1, False
            while sq[k]<x<sq[l] and not found:
                if x-sq[k] == sq[l]-x:
                    z, found = x-sq[k], True
                    if y-z in lookup and y+z in lookup:
                        print "x:", x, "y:", y, "z:", z
                        #x: 434657 y: 420968 z: 150568
                        done = True
                elif x-sq[k] > sq[l]-x: k += 1
                elif x-sq[k] < sq[l]-x: l -= 1
                else: print "Boing!"
            #print sq[i], sq[j]
        if done: break
    if done: break
print x+y+z #1006193
